package com.chj.gaoji.class15;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;

public class Code03_SmallestRangeCoveringElementsfromKLists {

	public static class Node {
		public int value;
		public int arrid;
		public int index;

		public Node(int v, int ai, int i) {
			value = v;
			arrid = ai;
			index = i;
		}
	}

	public static class NodeComparator implements Comparator<Node> {

		@Override
		public int compare(Node o1, Node o2) {
			return o1.value != o2.value ? o1.value - o2.value : o1.arrid - o2.arrid;
		}

	}

	public static int[] smallestRange(List<List<Integer>> nums) {
		int N = nums.size();
		TreeSet<Node> orderSet = new TreeSet<>(new NodeComparator());
		for (int arrid = 0; arrid < N; arrid++) {
			orderSet.add(new Node(nums.get(arrid).get(0), arrid, 0));
		}
		boolean set = false;
		int a = 0;
		int b = 0;
		while (orderSet.size() == N) {
			Node min = orderSet.first();
			Node max = orderSet.last();
			if (!set || (max.value - min.value < b - a)) {
				set = true;
				a = min.value;
				b = max.value;
			}
			min = orderSet.pollFirst();
			int arrid = min.arrid;
			int index = min.index + 1;
			if (index != nums.get(arrid).size()) {
				orderSet.add(new Node(nums.get(arrid).get(index), arrid, index));
			}
		}
		return new int[] { a, b };
	}

	public static void main(String[] args) {
		int[][] arr = { { 4, 10, 15, 24, 26 }, { 0, 9, 12, 20 }, { 5, 18, 22, 30 } };
		List<List<Integer>> nums = new ArrayList<List<Integer>>();
		for (int i = 0; i < arr.length; i++) {
			List<Integer> temp = new ArrayList<>();
			for (int j = 0; j < arr[i].length; j++) {
				temp.add(arr[i][j]);
			}

			nums.add(temp);
		}

		int[] ans = smallestRange(nums);
		System.out.println(ans);
	}
}
